Structure and Interpretation of Computer Programs (2e)/1
Section 1.1: The Elements of Programming Exercise 1.1 10 ''10'' (+ 5 3 4) ''12'' (- 9 1) ''8'' (+ (* 2 4) (- 4 6)) ''6'' (define a 3) ''a'' (define b (+ a 1)) ''b'' (+ a b (* a b)) ''19'' (= a b) ''#f'' (if (and (> b a) (< b (* a b))) b a) ''4'' (cond ((= a 4) 6) ((= b 4) (+ 6 7 a)) (else 25)) ''16'' (+ 2 (if (> b a) b a)) ''6'' (* (cond ((> a b) a) ((< a b) b) (else -1)) (+ a 1)) ''16'' Exercise 1.2 (/ (+ 5 (+ 4 (- 2 (- 3 (+ 6 (/ 4 5)))))) (* 3 (- 6 2) (- 2 7))) Exercise 1.3 This procedure uses a helper procedure, sum-squares: (define (sum-squares a b) (+ (* a a) (* b b))) We can now use this in the main procedure: (define (sum-larger-squares a b c) (cond ((= (min a b c) a) (sum-squares b c)) ((= (min a b c) b) (sum-squares a c)) ((= (min a b c) c) (sum-squares a c)))) Exercise 1.4 The if clause applies either + or -, depending on the value of b. If b is positive, (+ a b) is executed; otherwise, (- a b) is executed. This procedure essentially returns the sum of a and the absolute value of b. Exercise 1.5 Using applicative-order evaluation, p would keep calling itself forever, resulting in an infinite loop. This will most likely cause the Scheme interpreter to freeze. Using normal-order evaluation, x gets substituted with 0, so the (= x 0) clause becomes (= 0 0) and returns #t. The expanded expression then becomes (if #t 0 (p)) and returns 0. Exercise 1.6 Alyssa's new-if uses applicative-order instead of normal-order evaluation, so sqrt-iter will keep calling itself forever. Exercise 1.7 Assuming the appropriate helper procedures have been written, we can define our square root procedure. In our example, we name our procedure my-sqrt to prevent the built-in sqrt from being overwritten. Here, we use a starting guess of one. (define (my-sqrt x) (sqrt-iter 1 x)) (my-sqrt 25) ''5.00002317825395'' (my-sqrt 100) ''10.0000000001399'' (my-sqrt 10000) ''100.000000254907'' (my-sqrt 0.0000000001) ''0.031250001065625'' Very small numbers return incorrect results when they are less than the tolerance. Entering (my-sqrt 1e50) causes UCB Scheme to crash. For the second part of the problem, one simple solution is to check whether the approximation is close enough to the guess. This can be done by modifying the good-enough? procedure: (define (good-enough? guess x) (< (abs (- (improve guess x) guess)) (abs (* guess 0.001)))) This new version seems to produce more accurate results for small and large numbers: (my-sqrt 400) ''20.0001092577804'' (my-sqrt 0.000000000001) ''1.00045499080413e-006'' (my-sqrt 1e50) ''1.00087302912068e+025'' Exercise 1.8 (define (cube-improve guess x) (/ (+ (/ x (expt guess 2)) (* 2 guess)) 3)) (define (cube-good-enough? guess x) (< (abs (- (cube-improve guess x) guess)) (abs (* guess 0.001)))) (define (cbrt-iter guess x) (if (cube-good-enough? guess x) guess (cbrt-iter (cube-improve guess x) x))) (define (cube-root x) (cbrt-iter 1 x)) (cube-root 1000) ''10.0012053593377'' (cube-root 0.0000000000001) ''4.64201000474927e-005'' (cube-root 1e50) ''4.64195345097319e+016'' Section 1.2: Procedures and the Processes They Generate Exercise 1.9 The first version is a recursive process. (inc (+ (dec 4) 5)) (inc (+ 3 5)) (inc (inc (+ (dec 3) 5))) (inc (inc (+ 2 5))) (inc (inc (inc (+ (dec 2) 5)))) (inc (inc (inc (+ 1 5)))) (inc (inc (inc (inc (+ (dec 1) 5))))) (inc (inc (inc (inc (+ 0 5))))) (inc (inc (inc (inc 5)))) (inc (inc (inc 6))) (inc (inc 7)) (inc 8) ''9'' The second version is an iterative process. (+ (dec 4) (inc 5)) (+ 3 6) (+ (dec 3) (inc 6)) (+ 2 7) (+ (dec 2) (inc 7)) (+ 1 8) (+ (dec 1) (inc 8)) (+ 0 9) ''9'' Exercise 1.10 (A 1 10) ''1024'' (A 2 4) ''65536'' (A 3 3) ''65536'' The [[Wikipedia:Ackermann function|Ackermann function]] grows very fast. (A 2 5) will cause the Scheme interpreter to crash. The googolplex is ''completely unnoticeable'' in comparison to (A 2 6). (f n) produces f(n) = 2n. (g n) produces g(n) = 2n. (h n) produces h(n) = 2h(n-1), which is an exponential stack of 2's of height ''n''. Using [[Wikipedia:Knuth's up-arrow notation|Knuth's up-arrow notation]], this can be written as 2↑↑n. Section 1.3: Formulating Abstractions with Higher-Order Procedures